package com.hanxiaozhang.no3algorithm;

import java.util.*;
import java.util.function.BiConsumer;

/**
 * 〈一句话功能简述〉<br>
 * 〈Lru算法的Java实现〉
 *
 * @author hanxinghua
 * @create 2022/5/21
 * @since 1.0.0
 */
public class No3Lru {

    public static void main(String[] args) {

        LruByLinkedHashMap lruByLinkedHashMap = new LruByLinkedHashMap(4);
        lruByLinkedHashMap.put(1, 2);
        lruByLinkedHashMap.put(2, 2);
        lruByLinkedHashMap.put(3, 2);
        lruByLinkedHashMap.put(4, 2);
        lruByLinkedHashMap.put(5, 2);
        lruByLinkedHashMap.put(3, 1);
        System.out.println("---- lruByLinkedHashMap ----");
        lruByLinkedHashMap.println();


        LruByDoubleLinkedAndHashMap lruByDoubleLinkedAndHashMap = new LruByDoubleLinkedAndHashMap(4);
        lruByDoubleLinkedAndHashMap.put(1, 2);
        lruByDoubleLinkedAndHashMap.put(2, 2);
        lruByDoubleLinkedAndHashMap.put(3, 2);
        lruByDoubleLinkedAndHashMap.put(4, 2);
        lruByDoubleLinkedAndHashMap.put(5, 2);
        lruByDoubleLinkedAndHashMap.put(3, 1);
        System.out.println("---- lruByDoubleLinkedAndHashMap ----");
        lruByDoubleLinkedAndHashMap.println();

    }
}

/**
 * LRU算法使用LinkedHashMap实现
 */
class LruByLinkedHashMap {

    private Map<Integer, Integer> map = null;

    public LruByLinkedHashMap(int capacity) {
        // accessOrder设置为false时，按照插入顺序，设置为true时，按照访问顺序。
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {

            /**
             * 重写删除最年长元素的规则
             * @param eldest
             * @return
             */
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }


    public void println() {

        ArrayList list = new ArrayList(map.entrySet());
        ListIterator<Map.Entry<Integer, Integer>> it = list.listIterator(map.size());
        while (it.hasPrevious()) {
            Map.Entry<Integer, Integer> entry = it.previous();
            System.out.println("key is " + entry.getKey() + " value is " + entry.getValue());
        }
    }

}


/**
 * LRU算法使用双向链表+HashMap实现
 * <p>
 * 思路：
 * -维护一个双向链表，靠近链表尾部的结点是越早访问的，靠近头部的节点是最近访问的。
 * -如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
 * -如果此数据没有在缓存链表中，又可以分为两种情况：
 * --如果此时缓存未满，则将此结点直接插入到链表的头部
 * --如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
 */
class LruByDoubleLinkedAndHashMap {

    /**
     * 当前缓存容量
     */
    private int size;

    /**
     * 限制最大缓存容量
     */
    private int capacity;

    /**
     * 头结点
     */
    private Node head;

    /**
     * 尾节点
     */
    private Node tail;

    /**
     * 存储数据
     */
    private Map<Integer, Node> map = new HashMap();

    public LruByDoubleLinkedAndHashMap(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 初始化头尾节点
        this.head = new Node();
        this.tail = new Node();
        // 让头尾节点相联
        this.head.next = tail;
        this.tail.pre = head;
    }

    /**
     * 获取
     *
     * @param key
     * @return
     */
    public int get(int key) {
        Node node = map.get(key);
        // 不存在返回-1
        if (null == node) {
            return -1;
        }
        // 存在返回值，并且将当前节点移动到头
        moveNodeHead(node);
        return node.value;
    }

    /**
     * 添加
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Node node = map.get(key);
        // 不存在则插入，插入后判断当前容量是否大于限制最大容量
        if (null == node) {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            // 放入链表头部
            addNodeHead(newNode);
            size++;
            if (size > capacity) {
                // 删除尾结点
                Node tail = removeNodeTail();
                map.remove(tail.key);
            }
        } else {
            // 存在则覆盖，并且将当前节点移动到头
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            // 头部添加
            addNodeHead(newNode);
            moveNodeHead(node);
        }
    }


    public void println() {
        Node node = head.next;
        while (node != null && node != tail) {
            System.out.println("key is " + node.key + " value is " + node.value);
            node = node.next;
        }
    }


    /**
     * 放入链表的头部
     *
     * @param node
     */
    private void addNodeHead(Node node) {
        // 头节点的后继节点的前继，指向node
        head.next.pre = node;
        // node节点的后继，指向头结点的后继节点
        node.next = head.next;
        // 头节点的后继节点，指向node
        head.next = node;
        // node节点的前继，指向头结点
        node.pre = head;
    }

    /**
     * 将节点移动到链表的头部
     */
    private void moveNodeHead(Node node) {
        // 从原来位置删除
        // node的前继节点的后继，指向node后继
        node.pre.next = node.next;
        // node的后继节点的前继，指向node前继
        node.next.pre = node.pre;
    }

    /**
     * 删除链表的尾结点
     */
    private Node removeNodeTail() {
        // 获取尾节点的前继节点
        Node tailNode = tail.pre;
        // tailNode的前继节点的后继，指向尾节点
        tailNode.pre.next = tail;
        // 尾节点的前继，指向tailNode的前继节点
        tail.pre = tailNode.pre;
        return tailNode;
    }

    /**
     * 定义一个双向链表，实际的缓存
     */
    class Node {
        private int key;
        private int value;
        private Node pre;
        private Node next;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

